1. Field of Invention
This invention relates, in its most general aspects, to a computer system and to a method of operating that system, and to improvements in the performance of various operations within such a system. It also relates to a computer-readable storage medium. The computer system may be, may include, or may be part of, a virtual machine. The computer-readable storage medium may contain executable code or other instructions for programming the computer system/virtual machine. In particular, the invention relates to a method for automatic testing and verification of dynamically compiled code in a virtual machine.
2. Description of Related Art
In recent years, there have been developments in programming languages towards what is known as an object-oriented language. In these developments, concepts are regarded as xe2x80x98objectsxe2x80x99, each carrying with it a set of data, or attributes, pertinent to that object, as well as information relating to so-called xe2x80x98methodsxe2x80x99, that is functions or sub-routines, that can be performed on that object and its data. This is well known to those skilled in the art of computing and/or programming.
The advent and rapid advancement in the spread and availability of computers has led to the independent development of different types of systems, such as the IBM and IBM-compatible PC running IBM-DOS or MS-DOS or MS-Windows applications, the Apple Macintosh machines running their own Apple System operating system, or various Unix machines running their own Unix operating systems. This proliferation of independent systems has led to useful applications being available only in one format and not being capable of running on a machine for which the application was not designed.
Under such circumstances, programmers have devised software which xe2x80x98emulatesxe2x80x99 the host computer""s operating system so that a xe2x80x98foreignxe2x80x99 application can be made to run successfully in such a way that, as far as the user is concerned, the emulation is invisible. In other words, the user can perform all of the normal functions of say a Windows-based application on a Unix machine using a Unix-based operating system without noticing that he is doing so.
A particularly notable product of this type is that developed by Insignia Solutions of High Wycombe, GB and Santa Clara, Calif., USA and known under the name xe2x80x98SoftWindows 2.0 for Powermacxe2x80x99. This software enables a physical Macintosh computer to emulate a PC having an Intel 80486DX processor and 80487 maths co-processor plus memory, two hard disks, IBM-style keyboard, colour display and other features normally found on recent versions of the PC-type of computer.
Furthermore, there is an ever-increasing demand by the consumer for electronics gadgetry, communications and control systems which, like computers, have developed independently of one another and have led to incompatibility between operating systems and protocols. For example, remote-control devices for video players, tape players and CD players have similar functions, analogous to xe2x80x98play,xe2x80x99 xe2x80x98forward,xe2x80x99 xe2x80x98reverse,xe2x80x99 xe2x80x98pause,xe2x80x99 etc, but the codes for transmission between the remote control, or commander, operated by the user may not be compatible either between different types of equipment made by the same manufacturer or between the same types of equipment made by different manufacturers. There would be clear benefits of having software within the equipment which can produce for example the correct xe2x80x98playxe2x80x99 code based upon a xe2x80x98playxe2x80x99 command regardless of the specific hardware used in the equipment. Such software is commonly known as a xe2x80x98Virtual Machine.xe2x80x99
Other uses and applications are legion: for example, set-top boxes for decoding television transmissions, remote diagnostic equipment, in-car navigation systems and so-called xe2x80x98Personal Digital Assistants.xe2x80x99 Mobile telephones, for instance, can have a system upgrade downloaded to them from any service provider.
Emulation software packages tend to have certain features in common, notably that they are not general purpose but are dedicated. They are of most benefit in rapid development areas and have a distinct advantage in enabling manufacturers to cut costs. In particular, they can divorce software from the physical machine, i.e., the effect of the software in the physical machine can be altered by the emulating software without having to go into the machine""s native software to implement those changes.
The specific object-oriented language used in some of the implementations described later is that known as Java (registered trade mark to Sun Microsystems Corporation). Some of the following implementations will enable Java to be used in smaller devices than is currently possible because of the improved performance and/or reduced memory footprint. Future uses projected for embedded software (virtual machines) include computers worn on the body, office equipment, household appliances, and intelligent houses and cars.
While it is recognised that there are clear advantages in the use of virtual machines. especially those using object-oriented languages, there are naturally areas where it is important and/or beneficial for some of the operations that are carried out within the system to be optimised. These may include reducing the memory requirement, increasing the speed of operation, and improving the xe2x80x98transparencyxe2x80x99 of the system when embedded in another system. One of the principal aims of the inventions described herein is to provide a Virtual Machine which is optimised to work as quickly as possible within a memory constraint of, for example, less than 10, 5, 2 or even 1 Mbyte. Such a constraint is likely to be applicable, for example, to electronics gadgetry and other equipment where cost (or size) is a major constraint.
Errors in dynamically compiled code frequently manifest themselves a long time after the error actually occurred, making it difficult to identify the true cause. An error may appear benign when it occurs (for example an incorrect calculation which is not immediately used), but its effects may be disastrous at some future time or event (for example, when the incorrect value is used).
When changing and/or adding optimisations to a dynamic compiler, it is difficult to demonstrate that the code produced as a result is correct. The invention is therefore concerned with testing for such errors.
In one known technique, testing as such was not conducted in a forward-looking sense. Instead, when an error was noted, the process would be investigated backwards to locate the origin of the error. This technique was clearly open to the risk of potentially disastrous errors occurring unnoticed until too late.
In another known technique which is an improvement over the previous one just mentioned, two execution engines are used within the same process and their results are compared. One execution engine is the trusted implementation (the master) and the other is the implementation under test (the slave). This test process is limited to a singly-threaded application and can be both cumbersome and time-consuming, since the execution engines must be run in series. The process is to save the initial state (state 1), run part of the master, save the final state of the master (state 2), restore state 1, run part of the slave, then check the final state of the slave against the saved state 2 to detect discrepancies.
The testing technique implemented in Softwindows (by Insignia) was of such a type as just outlined. While effective for its purpose it would be fair to say that it was limited in that it was only applicable to single threaded environments and, when applied to a CPU emulator, had an executable that was simply enormous. The executables for the master and slave were in the same executable so testing had to be done in series. Moreover, the testing technique could itself introduce bugs and dissimilarities between master and slave. The points at which comparisons of state would have been carried out were largely only at transfers of control.
Techniques for identifying the cause of errors once identified tend to perturb the system under test, often to the extent of changing or removing (temporarily) the failure behaviour.
The object of the invention is therefore to provide a quicker and more reliable system and method for testing pieces of executable code, preferably executable code produced by a dynamic compiler.
A first aspect of the present invention provides a method of testing a first piece of computer code which is an implementation of a particular specification against a second piece of computer code which is a different implementation of the same specification, including the steps of: defining corresponding synchronisation points in both pieces of code; executing both pieces of code; and comparing the states produced by both pieces of code at the synchronisation points.
In many cases, the First piece of code can be a tested implementation of the specification (a xe2x80x98masterxe2x80x99), whilst the second piece of code can be an implementation under test (a xe2x80x98slavexe2x80x99).
If a discrepancy is found in the states produced, then it will indicate that since the previous synchronisation point the behaviour caused by the two pieces of code has differed. The code which has been executed by the slave since the last synchronisation point can easily be identified.
If a discrepancy is found, it indicates that one (or possibly both) pieces of code contains an error. The error is generally found in the slave if only because it is likely to be newer, more complex, and less tested than the trusted master, but nevertheless this method may identify an error in the trusted master provided that the slave is either correct or at least differently incorrect.
Preferably, the first and second pieces of code are executed by first and second different executables, respectively, e.g., a machine or machines having separate address systems and separate stacks.
This aspect of the invention is particularly applicable when the first and second pieces of code are executed by first and second different virtual machines, respectively, thus increasing efficiency. The virtual machines need not necessary employ the same architectures and/or operating systems. The system may operate independent processes and may optionally be concurrent.
In the case where the first and second pieces of code each include native methods or functions, at least one such native method or function required by the second piece of code may be executed by the first executable (e.g., the master) and the result thereof being returned to the second executable. In this case, the method preferably further includes the step of providing from the first executable to the second executable a list of such native methods or functions which are to be executed by the first executable.
In the comparing step for each synchronisation point in the first piece of code, the first executable (preferably the master) checks the state of the second executable at the corresponding synchronisation point in the second piece of code. For each synchronisation point in the second piece of code, the second executable (preferably the slave) saves the values of at least any of its state elements which are not up-to-date, updates the values of those state elements, transfers the values of its state elements to the first executable, and then restores the saved values of the updated state elements.
For increased efficiency, the first and second pieces of code are preferably executed in parallel.
This aspect of the invention is particularly applicable to pieces of code which are dynamically compiled.
The synchronisation points are preferably selected from: conditional transfers of control; method/function/procedure calls or returns; and backward transfers of control.
In the case where the first and second pieces of code each have plural threads of execution, a correspondence is preferably identified between corresponding threads produced by the first and second pieces of code, and in this case such corresponding synchronisation points are preferably defined in such corresponding threads.
Preferably, the programming language is Java and synchronisation is effected on a per thread basis. More especially, in that case there are preferably a plurality of asynchronously handled thread pairs.
Also, a correspondence is preferably identified between corresponding objects dynamically allocated by the first and second pieces of code.
A second aspect of this invention provides a computer system programmed to perform the method of the first aspect of the invention.
A third aspect of this invention provides a computer system for testing a first piece of computer code which is an implementation of a particular specification against a second piece of computer code which is a different implementation of the same specification, wherein: corresponding synchronisation points are defined in both pieces of code; and the system includes: means for executing both pieces of code; and means for comparing the states produced by both pieces of code at the synchronisation points.
A fourth aspect of this invention provides a computer system for testing a first piece of computer code which is an implementation of a particular specification against a second piece of computer code which is a different implementation of the same specification, wherein: corresponding synchronisation points are defined in both pieces of code; and the system includes: a first executable for executing the first piece of code; and a second executable for executing the second piece of code; the first executable also being operable to compare the states produced by both pieces of code at the synchronisation points.
In the fourth aspect of this invention, the first and second executables are preferably provided by first and second different virtual machines, respectively.
The systems according to the third or fourth aspects of the invention are preferably programmed to perform the method of the first aspect of this invention.
A fifth aspect of this invention provides a computer storage medium, or computer storage media, having recorded thereon a first piece of computer code which is an implementation of a particular specification and a second piece of computer code which is a different implementation of the same specification, wherein corresponding synchronisation points are defined in both pieces of code.
A sixth aspect of this invention provides a computer storage medium, or computer storage media, having recorded thereon a program to cause a computer system to perform the method of the first aspect of the invention or to operate in accordance with any of the second to fourth aspects of this invention.
Particularly where the specification is of an execution engine for Java bytecode, the two implementations are advantageously built into different virtual machines (VMs). The VM containing the trusted implementation is called the Master VM, and the VM containing the implementation under test is called the Slave VM. Both VMs execute the same application and communicate with each other at known synchronisation points to exchange and compare the states of the virtual machines.
Advantageously in the above systems and methods, the synchronisation points may be chosen (at least) in (partial) dependence upon (and preferably in proportion to) the length of code. This gives the dynamic compiler the best chance of performing the same optimisations as when not tinder test and hence reduces perturbation.
In a specific embodiment of the invention, the slave VM undergoes minimal perturbation, reducing the possibility of changing the failure behaviour. Also, the state acted on by each implementation is independent of the state acted on by the other. Furthermore, the Slave VM requires few extra resources for this invention, increasing its applicability.
In the embodiment of the invention, the onus on the untested implementation in the slave VM is reduced. As will become apparent the onus on the untested implementation will be simply to transmit to the trusted implementation the final states at synchronisation points, also to be described later. Rather than having to play an active role, the untested implementation is effectively passive and passes to the trusted implementation only data as requested by the trusted implementation. Both implementations will start at the same initial states so the synchronisation points will be predictable. Moreover, the trusted implementation will normally be run on a powerful target machine, so that the Master VM can be heavily instrumented, whereas the test implementation could be run on a smaller, perhaps a hand-held, target machine. It is not normally necessary to port the Master VM to the target machine on which the Slave VM is to be run.
The invention also provides a method of testing one implementation of a particular specification against a different implementation of the same specification, including the steps of:
defining corresponding synchronisation points in both implementations; executing the one implementation and the similar implementation; and comparing the states produced by both pieces of code at the synchronisation points.
The invention also provides a computer system for testing one implementation of a particular specification against a different implementation of the same specification, including means for defining corresponding synchronisation points in both implementations, means for executing implementations, and means for comparing the states produced by both implementations at the synchronisation points.
Any, some, or all of the features of any aspect of the invention may be applied to any other aspect.